Классификационные модели, которые мы рассматривали в предыдущих параграфах, нацелены непосредственно на оценку $P(Y \vert X)$. Такие модели называются дискриминативными.

К ним относится, например, логистическая регрессия: она предлагает оценку $\hat P(y=1 \vert x) = \sigma(w\^Tx)$. В процессе обучения дискриминативные модели подбирают разделяющую поверхность (гиперплоскость в случае логистической регрессии). Новые объекты дискриминативная модель классифицирует в зависимости от того, по какую сторону от разделяющей поверхности они лежат.

Например, обучившись на изображениях домашних кошек (y=0) и рысей (y=1), дискриминативная модель будет определять, новое изображение больше похоже на кошку или на рысь. При этом, если на вход такой модели дать изображение собаки (объект класса, которого не было в обучении, выброс), дискриминативная модель заведомо не сможет обнаружить, что это и не кошка, и не рысь, и отнесёт такой объект к одному из «знакомых» ей классов.

В этом параграфе мы поговорим о другой группе моделей, которые нацелены на оценку $P(X, Y) = P(X \vert Y)P(Y)$. Такая модель описала бы, как обычно выглядят кошки, как они могут выглядеть, а каких кошек точно не бывает. Так же она описала бы и рысей. Она также определила бы по обучающим данным, насколько изображения кошек встречаются чаще, чем изображения рысей, т.е. оценила бы $P(Y)$.

Генеративный и дискриминативный подходы к обучению

Если модель позволила точно оценить распределение $P(X \vert Y)$, с её помощью можно генерировать объекты из этого условного распределения, в нашем примере — изображения кошек и рысей соответственно.

А вместе распределение $P(X, Y)$ дало бы нам возможность генерировать изображения и кошек, и рысей, причём именно в той пропорции, в которой они встречаются в реальном мире. Поэтому модели, оценивающие $P(X, Y)$, называют генеративными. Ещё одно достоинство генеративных моделей — их способность находить выбросы в данных: объект $x$ можно считать выбросом, если $P(x \vert y)$ мало для каждого класса $y$.

Заметим, что находить выбросы с помощью генеративной модели можно и когда класс всего один — то есть никакие метки классов не доступны. Такая задача называется одноклассовой классификацией. Например, если у нас есть не размеченный датасет с аудиозаписями речи людей, то, обучив на нём генеративную модель, оценивающую в данном случае $P(X \vert Y)=P(X)$, мы сможем для нового аудио $x$ определить, похоже ли оно на аудиозапись человеческой речи (значение $P(x)$ велико), или это что-то другое: синтезированная речь, посторонний шум и т.п. (значение $P(x)$ мало).

Если мы знаем, что «выбросы», с которыми модели предстоит сталкиваться, — это, как правило, синтезированная речь, то, мы можем дополнить датасет вторым классом, состоящим из синтезированной речи, и смоделировать также распределение этого класса. Это позволит существенно увеличить качество детектирования таких выбросов.

Чтобы использовать генеративную модель для классификации, необходимо выразить $P(Y \vert X)$ через $P(X \vert Y)$ и $P(Y)$. Сделать это позволяет формула Байеса:

$$P(y \vert x) = \frac{P(x, y)}{\sum\limits_{y'\in Y} P(y')P(x \vert y')} = \frac{P(y)P(x \vert y)}{\sum\limits_{y'\in Y} P(y')P(x \vert y')}$$

Классификация в генеративных моделях осуществляется с помощью байесовского классификатора:

$$a(x) = \arg\max\limits_{y\in Y} P(y \vert x) = \arg\max\limits_{y\in Y} \frac{P(y)P(x \vert y)}{\sum\limits_{y'\in Y} P(y')P(x \vert y')} = \arg\max\limits_{y\in Y} P(y)P(x \vert y)$$

Оценить $P(Y)$, как правило, несложно. Для этого используют частотные оценки, полученные в обучающей выборке:

Выражение (1)

$$\hat P(Y=y) = \frac{\#(Y=y)}{N}$$

Отметим ещё раз, что использование генеративного подхода позволяет внедрять в модель априорные знания о $P(y)$. Это не очень впечатляет, когда речь идёт о бинарной классификации, но всё меняется, если рассмотреть задачу ASR (автоматического распознавания речи), в которой по записи голоса восстанавливается произносимый текст.

Таргетами здесь могут быть любые предложения или даже более развёрнутые тексты. При этом размеченных данных (запись, текст) обычно намного меньше, чем доступных текстов, и обученная на большом чисто текстовом корпусе языковая модель, которая будет оценивать вероятность того или иного предложения, может стать большим подспорьем, позволив из нескольких фонетически корректных наборов слов выбрать тот, который в большей степени похож на настоящее предложение.

Но как смоделировать распределение $P(X, Y)$? Пространство всех возможных функций распределения $P(X, Y)$ бесконечномерно, из-за чего оценить произвольное распределение с помощью конечной выборки невозможно. Поэтому перед оценкой $P(X, Y)$ на это распределение накладывают дополнительные ограничения. Некоторые простые примеры таких ограничений мы рассмотрим в следующих разделах.

Gaussian discriminant analysis

Модель гауссовского (или квадратичного) дискриминантного анализа (GDA) строится в предположении, что распределение объектов каждого класса $y$ подчиняется многомерному нормальному закону со средним $\mu_y$ и ковариационной матрицей $\Sigma_y$:

$$p(x \mid y)=\frac{1}{(2 \pi)^{n / 2}\left|\Sigma_y\right|^{1 / 2}} \exp \left(-\frac{1}{2}\left(x-\mu_y\right)^T \Sigma_y^{-1}\left(x-\mu_y\right)\right)$$

Тогда функция правдоподобия

$$\mathcal L(P(Y), \mu, \Sigma) = \prod_{i=1}^N p(x_i \vert y_i; \mu_{y_i}, \Sigma_{y_i})P(y_i)$$

достигает максимума при

$$\hat\mu_y = \frac{\sum\limits_{i=1}^N{x_i\mathbb{1}_{y_i=y}}}{\sum\limits_{i=1}^N\mathbb{1}_{y_i=y}},\hspace{5mm} \hat\Sigma_y = \frac{\sum\limits_{i=1}^N{(x_i - \hat\mu_{y})(x_i - \hat\mu_{y})^T \mathbb{1}_{y_i=y}}}{\sum\limits_{i=1}^N\mathbb{1}_{y_i=y}}$$

И $\hat P(Y)$, представленной выше см. выражение $(1)$.

Рассмотрим, как выглядит разделяющая поверхность в модели GDA. На поверхности, разделяющей классы $y_i$ и $y_j$ выполняется

$$P(y_i \vert x)=P(y_j \vert x) \Leftrightarrow$$

$$p(x \vert y_i)P(y_i) = p(x \vert y_j)P(y_j)\Leftrightarrow$$

$$\log p(x \vert y_i) + \log P(y_i) - \log p(x \vert y_j) - \log P(y_j) = 0\Leftrightarrow$$

Выражение (2)

$$\begin{equation} -\frac{1}{2}(x-\mu_{y_i})^T\Sigma_{y_i}^{-1} (x-\mu_{y_i})-\log (2\pi)^{n/2}|\Sigma_{y_i}|^{1/2} + \log P(y_i) + \frac{1}{2}(x-\mu_{y_j})^T\Sigma_{y_j}^{-1} (x-\mu_{y_j}) + \log (2\pi)^{n/2}|\Sigma_{y_j}|^{1/2} - \log P(y_j) = 0 \end{equation}$$

Поскольку левая часть уравнения (2) квадратична по $x$, разделяющая поверхность между двумя классами будет представлять из себя гиперповерхность порядка 2. Пример разделяющей поверхности многоклассовой модели GDA приведён на рис.

Плотность классов и разделяющая поверхность в многоклассовой модели LDA см. рисунок.

Linear Discriminant Analysis

В выражении (2) член второго порядка $x^T (\Sigma_{y_j}^{-1} - \Sigma_{y_i}^{-1})x$ зануляется при $\Sigma_{y_i}=\Sigma_{y_j}$. Таким образом, если дополнительно предположить, что все классы имеют общую ковариационную матрицу $\Sigma$, разделяющая поверхность между любыми двумя классами будет линейной (см. рисунок). Поэтому такая модель называется линейным дискриминантным анализом (LDA).

На этапе обучения единственное отличие модели LDA от GDA состоит в оценке ковариационной матрицы:

$$\hat \Sigma = \frac{1}{N}\sum\limits_{i=1}^N{(x_i - \hat\mu_{y_i})(x_i - \hat\mu_{y_i})^T}$$

Заметим, что в модели GDA для каждого класса требовалось оценить порядка $d^2$ параметров. Это может привести к переобучению в случае, если размерность пространства признаков велика, а некоторые классы представлены в обучающей выборке малым количеством объектов. В LDA для каждого класса требуется оценить лишь порядка $d$ параметров (значение $P(y)$ и элементы вектора $\mu_y$), и ещё $d^2$ общих для всех классов параметров (элементы матрицы $\Sigma$).

Таким образом, основное преимущество модели LDA перед GDA — её меньшая склонность к переобучению, недостаток — линейная разделяющая поверхность.

Метод наивного байеса

Предположим, что признаки $X$ объектов каждого класса $y$ — независимые случайные величины:

$$\forall y\in Y \hspace{2mm} \forall U, V: U\sqcup V = \{1, ... d\}, \hspace{2mm} \forall x^u\subset \mathbb R^{|U|}, x^v\subset \mathbb R^{|V|}$$

$$P(X^U\in x^u, X^V\in x^v|Y=y) = P(X^U\in x^u|Y=y)P(X^V\in x^u|Y=y).$$

В таком случае говорят, что величины $X$ условно независимы относительно $Y$. Тогда справедливо

Выражение (3)

$$\begin{equation} P(X \vert Y) = P(X^1, X^2, ..., X^d \vert Y) = P(X^1 \vert Y)P(X^2, ..., X^d \vert Y) = ... = P(X^1 \vert Y)P(X^2 \vert Y)...P(X^d \vert Y) \end{equation}$$

То есть для того, чтобы оценить плотность многомерного распределения $P(X \vert Y)$ достаточно оценить плотности одномерных распределений $P(X^i \vert Y)$, см. рисунок.

На рисунке приведён пример условно независимых относительно $Y$ случайных величин $X^1, X^2$. Для оценки плотности двумерных распределений объектов классов достаточно оценить плотности маргинальных распределений, изображённые графиками вдоль осей.

Рассмотрим пример. Пусть решается задача классификации отзывов об интернет-магазине на 2 категории: $Y=0$ — отрицательный отзыв, клиент остался не доволен, и $Y=1$ — положительный отзыв. Пусть признак $X^w$ равен 1, если слово $w$ присутствует в отзыве, и 0 иначе. Тогда условие выражения $(3)$ означает, что, в частности, наличие или отсутствие слова «дозвониться» в отрицательном отзыве не влияет на вероятность наличия в этом отзыве слова «телефон».

На практике в процессе feature engineering почти всегда создаётся много похожих признаков, и условно независимые признаки можно встретить очень редко. Поэтому генеративную модель, построенную в предположении условия выражения $(3)$, называют наивным байесовским классификатором (Naive Bayes classifier, NB).

Обучение модели NB заключается в оценке распределений $P(Y)$ и $P(X^i \vert Y)$. Для $P(Y)$ можно использовать частотную оценку выражения $(1)$. $P(X^i \vert y)$ — одномерное распределение. Рассмотрим несколько способов оценки одномерного распределения.

Оценка одномерного распределения

Пусть мы хотим оценить одномерное распределение $P(X)$.

Если распределение $P(X)$ дискретное, требуется оценить его функцию массы, то есть вероятность того, что величина $X$ примет значение $x_j$. Метод максимума правдоподобия приводит к частотной оценке:

Выражение (4)

$$\hat P(X = x_j) = \frac{\#(X = x_j)}{N}$$

Где $N$ — размер выборки, по которой оценивается распределение $X$ (количество объектов класса $y$ в случае оценки плотности класса $y$).

При этом может оказаться, что некоторое значение $x_j$ ни разу не встречается в обучающей выборке. Например, в случае классификации отзывов методом Наивного Байеса, слово «амбивалентно» не встретилось ни в одном положительном отзыве, но встретилось в отрицательных. Тогда использование оценки выражения $(4)$ приведёт к тому, что все отзывы с этим словом будут определяться NB как отрицательные с вероятностью 1. Чтобы избежать принятия таких радикальных решений при недостатке статистики, используют сглаживание Лапласа:

$$\hat P(X = x_j) = \frac{\#(X = x_j) + \alpha}{N + m\alpha},$$

где $m$ — количество различных значений, принимаемых случайной величиной $X$, $\alpha$ — гиперпараметр.

Для оценки плотности $p$ абсолютно непрерывного распределения в точке $a$ можно разделить количество объектов обучающей выборки в окрестности точки $a$ на размер этой окрестности:

$$\hat p(a) = \frac{\sum\limits_{j}\mathbb{1}_{a - h < X_j < a + h}}{2h} = \frac{\sum\limits_{j}\mathbb{1}_{-h < X_j - a < h}}{2h}.$$

Обычно объекты, лежащие дальше от точки $a$, учитывают с меньшим весом. Таким образом, оценка плотности приобретает вид

$$\hat p(a) = \frac{\sum\limits_{j}K_h(X_j - a)}{2h},$$

где функция $K_h$, называемая ядром, обычно имеет носитель $(-h, h)$ (см. рисунок ниже). Такой способ оценки плотности называют непараметрическим.

Результат оценки плотности с разными ядрами. Использованы изображения из:

При параметрической оценке плотности предполагают, что искомое распределение лежит в параметризованном классе, и подбирают значения параметров при помощи метода максимума правдоподобия. Например, предположим, что искомое распределение нормальное. Тогда функция его плотности имеет вид

$$p(x) = \frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)$$

Таким образом, чтобы оценить плотность $p(x)$, достаточно оценить параметры $\mu, \sigma$. Метод максимума правдоподобия в этом случае даст такие оценки:

$\hat\mu = \overline X$ — выборочное среднее, $\hat\sigma = \sqrt{\frac{1}{N}\sum_{j=1}^N (X_j - \overline X)}$ — выборочное стандартное отклонение.

Если в модели NB распределения всех признаков объектов каждого класса нормальные, оценив параметры этих распределений, мы сможем каждый класс $y$ описать нормальным распределением со средним $\mu_p$ и диагональной ковариационной матрицей, значения на диагонали которой обозначим $\sigma_p$.

Таким образом, полученная модель (Gaussian Naive Bayes, GNB) эквивалентна модели GDA с дополнительным ограничением на диагональность ковариационных матриц.

Наивный байесовский подход и логистическая регрессия

Предположим теперь, что в модели GNB класса всего 2, причём соответствующие им ковариационные матрицы совпадают, как это было в модели LDA. Таким образом $\sigma_0 = \sigma_1 = \sigma$.

Посмотрим, как будет выглядеть $P(Y \vert X)$ в этом случае. По теореме Байеса имеем

$$P(Y=1 \vert X) = \frac{P(Y = 1)P(X \vert Y = 1)}{P(Y = 1)P(X \vert Y = 1) + P(Y = 0)P(X \vert Y = 0)}$$

Разделим числитель и знаменатель полученного выражения на числитель:

$$P(Y=1 \vert X) = \frac{1}{1 + \frac{P(Y = 0)P(X \vert Y = 0)}{P(Y = 1)P(X \vert Y = 1)}} = \frac{1}{1 + \exp\left(\ln\frac{P(Y=0)P(X \vert Y=0)}{P(Y=1)P(X \vert Y=1)}\right)}$$

Из условной независимости $X^i$ относительно $Y$ получаем

Формула (5)

$$\begin{equation} P(Y=1 \vert X) = \frac{1}{1 + \exp\left(\ln\frac{P(Y=0)}{P(Y=1)} + \sum\limits_{i=1}^d \ln\frac{P(X^i \vert Y=0)}{P(X^i \vert Y=1)}\right)} \end{equation}$$

Перепишем сумму в знаменателе, воспользовавшись формулой плотности нормального распределения

$$\sum\limits_{i=1}^d \ln\frac{P(X^i \vert Y=0)}{P(X^i \vert Y=1)} = \sum\limits_{i=1}^d \ln\frac{\frac{1}{\sqrt{2\pi\sigma_i^2}}\exp \left(\frac{-(X^i - \mu_{0,i})^2}{2\sigma_i^2}\right)}{\frac{1}{\sqrt{2\pi\sigma_i^2}}\exp \left(\frac{-(X^i - \mu_{1,i})^2}{2\sigma_i^2}\right)}$$

$$= \sum\limits_{i=1}^d \frac{\left(X^i - \mu_{1, i}\right)^2 - \left(X^i - \mu_{0, i}\right)^2}{2\sigma_i^2}= \sum\limits_{i=1}^d \left(\frac{\mu_{0, i} - \mu_{1, i}}{\sigma_i^2}X^i + \frac{\mu_{1, i} ^ 2 - \mu_{0, i} ^ 2}{2\sigma_i^2}\right)$$

Подставляя это выражение в формулу (5) , получаем

$$P(Y=1 \vert X) = \frac{1}{1 + \exp\left(\ln\frac{P(Y=0)}{P(Y=1)} + \sum\limits_{i=1}^d \left(\frac{\mu_{0, i} - \mu_{1, i}}{\sigma_i^2}X^i + \frac{\mu_{1, i} ^ 2 - \mu_{0, i} ^ 2}{2\sigma_i^2}\right)\right)}$$

Таким образом, $P(Y=1 \vert X)$ представляется в GNB с общей ковариационной матрицей в таком же виде, как в модели логистической регрессии:

Формула (6)

$$\begin{equation} P(Y=1 \vert X) = \frac{1}{1 + \exp\left(w_0 + \sum\limits_{i=1}^d w_i X^i\right)} \end{equation}$$

где в случае GNB

$$w_0 = \ln\frac{P(Y=1)}{P(Y=0)} +\sum\limits_{i=1}^d\frac{\mu_{1, i} ^ 2 - \mu_{0, i} ^ 2}{2\sigma_i^2}, \quad w_i = \frac{\mu_{0, i} - \mu_{1, i}}{\sigma_i^2} \hspace{1cm} i=1, \dots, l$$

Однако это не значит, что модели эквивалентны: модель логистической регрессии накладывает менее строгие ограничения на распределение $P(X, Y)$, чем GNB.

Так, $X^i$ могут не являться условно независимыми относительно $Y$, а распределения $P(X \vert Y=y)$ могут не удовлетворять нормальному закону, но $P(y \vert X)$ может при этом всё равно представляться в виде формулы (6) .

В этом случае использование метода логистической регрессии предпочтительнее. С другой стороны, если есть основания полагать, что требования GNB выполняются, то от GNB можно ожидать более высокого качества классификации по сравнению с логистической регрессией.